package com.lun.medium;

import java.util.ArrayList;
import java.util.List;

public class Subsets {
	// 方法一：回溯算法
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		backtracking(path, nums, 0, result);
		return result;
	}

	private void backtracking(List<Integer> path, int[] originalArray, int startIndex, List<List<Integer>> result) {
		result.add(new ArrayList<>(path));

		//本if语块可以移除
		if(startIndex == originalArray.length) {
			return;
		}

		for (int i = startIndex; i < originalArray.length; i++) {
			path.add(originalArray[i]);
			backtracking(path, originalArray, i + 1, result);
			path.remove(path.size() - 1);
		}
	}

	// 方法二：BFS or DP??
	public List<List<Integer>> subsets2(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		result.add(new ArrayList<>());

		for (int i : nums) {
			int size = result.size();
			for (int j = 0; j < size; j++) {
				List<Integer> temp = new ArrayList<>(result.get(j));
				temp.add(i);
				result.add(temp);
			}
		}

		return result;
	}

	// 方法三：位操作
	public List<List<Integer>> subsets3(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		int total = 1 << nums.length; // 小心溢出
		for (int i = 0; i < total; i++) {
			List<Integer> tempList = new ArrayList<>();
			for (int j = i, count = 0; j > 0; j >>>= 1, count++) {
				if ((j & 1) == 1)
					tempList.add(nums[count]);
			}
			result.add(tempList);
		}
		return result;
	}

}
